package cn.leetcode;

import java.util.*;

public class Code15 {

    public static void main(String[] args) {
        int[] arr = {2,-3,0,-2,-5,-5,-4,1,2,-2,2,0,2,-4,5,5,-10};
        List<List<Integer>> lists = threeSumPlus(arr);
        System.out.println(lists);
    }


    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        Map<String, String> map = new HashMap<>();
        for(int i=0; i< nums.length; i++){
            int a = nums[i];
            for(int j=i+1; j< nums.length; j++){
                int b = nums[j];
                for(int k=j+1; k< nums.length; k++){
                    int c = nums[k];
                    if(a + b + c == 0){
                        List<Integer> list = new ArrayList<>();
                        list.add(a);
                        list.add(b);
                        list.add(c);
                        String string = String.valueOf(list.get(0)) + list.get(1) + list.get(2);
                        String s = map.get(string);
                        if(s == null){
                            map.put(string, string);
                            result.add(list);
                        }
                    }
                }
            }
        }
        return result;
    }


    public static List<List<Integer>> threeSumPlus(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int flagNum = nums[0];
        for(int i=0; i<nums.length-2; i++){
            if(i > 0 && flagNum == nums[i]){
                continue;
            }else{
                flagNum = nums[i];
            }
            int left = i + 1;
            int right = nums.length - 1;
            int leftNum = nums[left];
            int rightNum = nums[right];
            while (left < right){
                if(left > i+1 && leftNum == nums[left]){
                    left++;
                    continue;
                }
                if(right < nums.length - 1 && rightNum == nums[right]){
                    right--;
                    continue;
                }
                if(nums[left] + nums[right] + flagNum == 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(flagNum);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    leftNum = nums[left];
                    left++;
                    rightNum = nums[right];
                    right--;
                } else if (nums[left] + nums[right] + flagNum < 0) {
                    leftNum = nums[left];
                    left++;
                } else {
                    rightNum = nums[right];
                    right--;
                }
            }
        }
        return result;
    }
}


